package com.sheng.leetcode.year2022.swordfingeroffer.day15;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author liusheng
 * @date 2022/09/14
 *<p>
 * 剑指 Offer 36. 二叉搜索树与双向链表<p>
 *<p>
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。<p>
 * 为了让您更好地理解问题，以下面的二叉搜索树为例：<p>
 * 我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。<p>
 * 对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。<p>
 * 下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。<p>
 * 特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。<p>
 * 还需要返回链表中的第一个节点的指针。<p>
 *<p>
 * 注意：本题与主站 426 题相同：<a href="https://leetcode-cn.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/">...</a><p>
 *<p>
 * 注意：此题对比原题有改动。<p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class Sword0036 {

    @Test
    public void test01() {
//        Node root = new Node(4);
//        Node left = new Node(2);
//        left.left = new Node(1);
//        left.right = new Node(3);
//        root.left = left;
//        root.right = new Node(5);

        Node root = new Node(1);
        System.out.println(new Solution36().treeToDoublyList(root));
    }
}
//class Solution36 {
//    public Node treeToDoublyList(Node root) {
//        if (root == null) {
//            return null;
//        }
//        // 思路：就是一个中序遍历
//        Node head = new Node();
//        List<Node> list = new ArrayList<>();
//        // 遍历
//        ergodic(root, list);
//        // 遍历完后集合中元素的顺序即为中序遍历的顺序
//        if (list.size() == 1) {
//            head = list.get(0);
//            head.left = list.get(0);
//            head.right = list.get(0);
//        } else {
//            // 添加到head中
//            for (int i = 0; i < list.size(); i++) {
//                head = list.get(i);
//                if (i == 0) {
//                    head.left = list.get(list.size() - 1);
//                    head.right = list.get(i + 1);
//                } else if (i == list.size() - 1) {
//                    head.left = list.get(i - 1);
//                    head.right = list.get(0);
//                } else {
//                    head.left = list.get(i - 1);
//                    head.right = list.get(i + 1);
//                }
//                head = head.right;
//            }
//        }
//        return head;
//    }
//
//    public void ergodic(Node root, List<Node> list) {
//        if (root == null) {
//            return;
//        }
//        ergodic(root.left, list);
//        list.add(root);
//        ergodic(root.right, list);
//    }
//}

class Solution36 {
    // 头结点
    Node head;
    // 尾结点
    Node pre;
    public Node treeToDoublyList(Node root) {
        if (root == null) {
            return null;
        }
        // 在遍历的时候进行添加操作
        ergodic(root);
        // 将头结点的前一个结点设为尾结点，将尾结点的后一个结点设为头结点
        head.left = pre;
        pre.right = head;
        return head;
    }

    public void ergodic(Node root) {
        if (root == null) {
            return;
        }
        // 优先遍历左结点，最左结点为head结点
        ergodic(root.left);
        if (pre != null) {
            // 尾结点的后一个结点设置为当前结点root
            pre.right = root;
        } else {
            // 如果pre为空时，证明找到了第一个结点，赋值给head
            head = root;
        }
        // 将当前结点的前结点改为pre，如果是第一个结点时，此时为空
        root.left = pre;
        // 将尾结点的后一个结点设为当前结点root后，又将当前结点root设置为新的尾结点
        pre = root;
        ergodic(root.right);
    }
}
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
